The present invention relates to content addressable memory (CAM) arrays. More specifically, the present invention relates to quad (i.e., four-state) CAM cells and methods for operating these cells in a CAM array.
Unlike conventional random access memory (RAM) arrays, CAM arrays include memory cells that are addressed in response to their content, rather than by a physical address within a RAM array. That is, data words stored in a RAM array are accessed by applying address signals to the RAM array input terminals. In response to each unique set of address signals, a RAM array outputs a data value that is read from a portion of the RAM array designated by the address. In contrast, a CAM array receives a data value that is compared with all of the data values stored in rows of the CAM array. In response to each unique data value applied to the CAM array input terminals, the rows of CAM cells within the CAM array assert or de-assert associated match signals indicating whether or not one or more data values stored in the CAM cell rows match the applied data value.
CAM arrays are useful in many applications, such as search engines. For example, assume an employee list is searched to identify all employees with the first name xe2x80x9cJohnxe2x80x9d. The first names are written into a CAM array such that they are stored in a predetermined order (e.g., according to employee number). The compare data value (xe2x80x9cJohnxe2x80x9d) is then applied to the CAM input terminals. When one or more stored data values match the compare data value (a match condition), the match line coupled to the one or more matching rows of CAM cells generates a match value (e.g., a logic high value) output signal. The rows having CAM cells having stored data values that do not match the compare data value (a no-match condition) generate a no-match value (e.g., a logic low value) output signal on the associated match lines. By identifying which rows have associated high match lines, and comparing those row numbers with the employee number list, all employees named xe2x80x9cJohnxe2x80x9d are identified. Note that some CAM arrays generate a logic low value as a match value output signal. In contrast, to search a RAM array containing the same employee list, a series of addresses must be applied to the RAM array so that each stored data value is read out and compared with the xe2x80x9cJohnxe2x80x9d data value. Because each RAM read operation takes one clock cycle, a relatively large amount of time is required to read and compare a particular data value with all data values stored in a RAM array.
Two commonly-used CAM cells are binary CAM cells and ternary CAM cells, whose names are derived from the number of data values that they store.
Binary CAM cells stores one of two logic values: a logic high value or a logic low value. When an applied data value (e.g., logic high) is equal to the logic value stored by a binary CAM cell, then a match signal is transmitted on a match line connected to the binary CAM cell (e.g., the match line is maintained in a high voltage state). When all applied data values of an applied search term (e.g., xe2x80x9cJohnxe2x80x9d) are applied to a row of binary CAM cells collectively storing the term, then the match line connected to that row of binary CAM cells indicated the match. Conversely, when an applied data value is not equal to the logic value stored in a binary CAM cell, then a no-match signal is transmitted on the match line (e.g., the binary CAM cell discharges the match line to ground). This no-match signal is applied to the match line even if other stored data values match the applied data values (e.g., the applied search term xe2x80x9cJohnxe2x80x9d is compared to the stored term xe2x80x9cJoanxe2x80x9d).
A limitation associated with binary CAM cells arises when an xe2x80x9copen-endedxe2x80x9d search is desired. An xe2x80x9copen-endedxe2x80x9d search includes one or more specific data values that must be matched by the stored data values, and one or more non-specific data values, which are referred to herein as xe2x80x9cdon""t carexe2x80x9d data values, that need not be matched by the stored data value. For example, instead of searching only for employees named xe2x80x9cJohnxe2x80x9d, it may be desirable to search for any variation on xe2x80x9cJohnxe2x80x9d, such as xe2x80x9cJonxe2x80x9d, xe2x80x9cJohannxe2x80x9d, xe2x80x9cJohnnyxe2x80x9d, etc. In this example, an open-ended search might search for the first two letters xe2x80x9cJoxe2x80x9d, and ignore any subsequent letters in the data word (i.e., the don""t care values). Such an open-ended search is possible using binary CAM cells, but requires pre-processing of the stored data values and/or the applied data values such that, for example, all logic high values or all logic low values are stored/compared in the xe2x80x9cdon""t carexe2x80x9d letter locations.
Ternary CAM cells address the limitations of binary CAM cells by allowing a user to store one of three logic values: a logic high value, a logic low value, and a don""t care logic value. The don""t care logic value maintains the match signal whether the applied data value is a logic high value or a logic low value, thereby avoiding the need for pre-processing of the applied data value. For example, the name xe2x80x9cJohnxe2x80x9d may be stored as xe2x80x9cJ-o-DC-DC . . . DCxe2x80x9d, where xe2x80x9cDCxe2x80x9d represents a don""t care logic value. Similarly, the name xe2x80x9cJohnnyxe2x80x9d may be stored as xe2x80x9cJ-o-DC-DC . . . DCxe2x80x9d. Accordingly, in the above-mentioned open-ended search for all variations of the name xe2x80x9cJohnxe2x80x9d (i.e., xe2x80x9cJoxe2x80x9d), match signals are generated by both the row containing xe2x80x9cJohnxe2x80x9d (wherein the letters xe2x80x9chnxe2x80x9d are replaced with don""t care logic values) and xe2x80x9cJohnnyxe2x80x9d (wherein the letters xe2x80x9chnnyxe2x80x9d are replaced with don""t care logic values).
A problem with ternary CAM cells is that the logic high and logic low values associated with a data bit are lost when the data bit is stored as a don""t care logic value in a ternary CAM cell. That is, using the example provided above, assume that several employee names are stored in a CAM array made up of ternary CAM cells such that don""t care logic values are used in place of all letters after the second letter of each name. Assume also that both the name xe2x80x9cJohnxe2x80x9d and the name xe2x80x9cJoanxe2x80x9d are stored in the CAM array as xe2x80x9cJ-o-DC-DCxe2x80x9d. Under these conditions, both the names xe2x80x9cJohnxe2x80x9d and xe2x80x9cJoanxe2x80x9d would generate a match signal using the open-ended search for xe2x80x9cJoxe2x80x9d. When this occurs, it is not possible to read out the names from the CAM array to determine which matching row contains xe2x80x9cJohnxe2x80x9d and which matching row contains xe2x80x9cJoanxe2x80x9d.
Accordingly, what is needed is a four-state (herein referred to a xe2x80x9cquadxe2x80x9d) CAM cell that stores a logic low value, a logic high value, a logic low don""t care value, and a logic high don""t care value, thereby allowing the original data value (either logic high or logic low) to be stored in the CAM array. Such a quad CAM cell would facilitate storing, for example, both the name xe2x80x9cJohnxe2x80x9d and the name xe2x80x9cJoanxe2x80x9d as xe2x80x9cJ-o-DC-DCxe2x80x9d for comparison purposes, but also would retain the original data values xe2x80x9chnxe2x80x9d and xe2x80x9canxe2x80x9d, respectively, for post-comparison analysis. In addition, what is needed is a quad CAM cell that requires a minimum cell size, thereby minimizing the overall size of a CAM device incorporating an array of the quad CAM cells.
The present invention is directed to four-state (quad) CAM cells having a minimal cell size. The quad CAM cells of the present invention store one of four logic values: a logic high value, a logic low value, a logic high don""t care value, and a logic low don""t care value. Accordingly, the quad CAM cell of the present invention beneficially stores a data bit (e.g., a logic high value or a logic low value) of an original data word while allowing the data value to be designated as don""t care for comparison operations. As a result, as distinguished from ternary CAM cells, the data value can be read from the quad CAM cell after the comparison operation.
In accordance with an aspect of the present invention, the quad CAM cells are produced using a minimum number of transistors, thereby minimizing the cell size so that a CAM array incorporating the quad CAM cells requires a minimal amount of chip area.
Each quad CAM cell includes a first memory cell, a second memory cell, a comparator circuit, and a control switch. The first memory cell stores a data value (i.e., logic high value or logic low value), and transmits this stored data value to the comparator circuit. The second memory cell stores a care/don""t care data value that is transmitted to the control switch. Portions of the comparator circuit and the control switch form a discharge path between a match line and a discharge line connected to the quad CAM cell. The control switch is controlled by the care/don""t care value to open/close a first part of the discharge path. The comparator circuit is controlled to open a second part of the discharge path when, for example, the stored data value is equal to an applied data value. For example, in an embodiment where the match line is discharged to indicate a no-match condition, a xe2x80x9ccarexe2x80x9d value (i.e., the opposite of a don""t care value) stored in the second memory cell causes the control switch to open the first part of the discharge path, and when the comparator circuit opens the second part of the signal path when the stored data value transmitted from the first memory cell is different from the applied data value, thereby discharging the match line to the discharge line. Conversely, when the second memory cell stores a don""t care data value, or when the applied data value matches the stored data value, then the signal path remains closed and the match line remains charged.
Several specific embodiments of quad CAM cells according to the present invention are disclosed. In each disclosed embodiment, the first memory cell is implemented as an SRAM cell including a latch for storing the stored data value at a first node, and an inverse of the stored data value at a second node. In a first disclosed embodiment, the comparator circuit includes pass transistors connected in series between the control circuit and the discharge line, with the gate terminals of the pass transistors respectively connected to the first memory cell and a data line. In a second disclosed embodiment, pass transistors of the comparator circuit are connected in series between the control circuit and the match line. In a third disclosed embodiment, the comparator circuit is separated into two parts that are arranged such that the control circuit is located between and connected in series with the two parts between the discharge line and the match line. In a fourth disclosed embodiment, the comparator circuit includes a first pass transistor connected in series with the control circuit between the match line and the discharge line, and an additional pass transistor connected between the data line and the first pass transistor, and having a gate terminal controlled by the first memory cell.